package com.eddie.tenalgorithm.greedy;

import java.util.*;

/**
 * @author Eddie
 * @date 2022/08/16 14:34
 **/
public class GreedyAlgorithm {
    public static void main(String[] args) {
        GreedyAlgorithm ga = new GreedyAlgorithm();

        //创建广播电台,放入到Map中
        Map<String, Set<String>> broadcasts = new HashMap<>(4);
        //将各个电台放入broadcasts
        Set<String> set1 = new HashSet<>();
        set1.add("杭州");
        set1.add("北京");
        set1.add("上海");
        set1.add("天津");

        Set<String> set2 = new HashSet<>();
        set2.add("广州");
        set2.add("北京");
        set2.add("上海");
        set2.add("天津");

        Set<String> set3 = new HashSet<>();
        set3.add("成都");
        set3.add("武汉");
        set3.add("杭州");

        Set<String> set4 = new HashSet<>();
        set4.add("上海");
        set4.add("天津");

        Set<String> set5 = new HashSet<>();
        set5.add("广州");
        set5.add("杭州");
        set5.add("大连");

        //加入到map中
        broadcasts.put("K1", set1);
        broadcasts.put("K2", set2);
        broadcasts.put("K3", set3);
        broadcasts.put("K4", set4);
        broadcasts.put("K5", set5);

        List<String> selects = ga.greedy(broadcasts);

        System.out.println(selects);
    }

    public List<String> greedy(Map<String, Set<String>> broadcasts){
        //allAreas存放所有地区
        Set<String> allAreas = new HashSet<>();
        for(Map.Entry<String, Set<String>> entry: broadcasts.entrySet()){
            Set<String> area = entry.getValue();
            allAreas.addAll(area);
        }


        //创建ArrayList集合,存放选择的电台的集合
        List<String> selects = new ArrayList<>();

        //定义一个临时的集合,在遍历过程中,存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        Set<String> tempSet = new HashSet<>();

        /*
            定义一个maxKey,保存在一次遍历过程中,能够覆盖最大未覆盖的地区对应的电台的key
            如果maxKey不为null,则加入到selects中
         */
        String maxKey;
        //定义一个maxKey临时的集合,在遍历过程中,maxKey覆盖的地区和当前还没有覆盖的地区的交集
        Set<String> tempMaxKeySet = new HashSet<>();

        //如果allAreas不为空,则表示还没有覆盖到所有地区
        while(!allAreas.isEmpty()){
            maxKey = null;
            tempMaxKeySet.clear();

            //遍历broadcasts,取出对应的key
            for(String key: broadcasts.keySet()){
                tempSet.clear();//每一次都需要清空临时集合

                //当前key所能覆盖的地区
                Set<String> area = broadcasts.get(key);
                tempSet.addAll(area);
                //求出tempSet和allAreas的交集并赋给tempSet
                tempSet.retainAll(allAreas);
                /*
                    如果当前这个集合包含未覆盖地区的数量比maxKey指向的集合包含未覆盖地区的数量还多
                    就需要重置maxKey和它指向的集合包含未覆盖地区集合
                    tempSet.size() > tempMaxKeySet.size()体现贪心算法的特点,每次都选择最优的
                 */
                if(tempSet.size() > 0 && (maxKey == null || tempSet.size() > tempMaxKeySet.size())){
                    //清空,防止数据间影响
                    tempMaxKeySet.clear();

                    maxKey = key;
                    //maxKey覆盖的地区和当前还没有覆盖的地区的交集
                    Set<String> area2 = broadcasts.get(maxKey);
                    tempMaxKeySet.addAll(area2);
                    tempMaxKeySet.retainAll(allAreas);
                }
            }

            //maxKey != null,就应该将maxKey加入selects中
            if(maxKey != null){
                selects.add(maxKey);
                //将maxKey指向的广播电台覆盖的地区从allAreas中去掉
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }

        return selects;
    }
}
